using System;
using System.Collections.Generic;
using System.Text;

namespace Ltf.Diffs
{
	public class Nhunker
	{
		Dictionary<char, List<int>> charPositions;

		public int TestCounter;

		public Nhunker()
		{
			TestCounter = 0;
		}

		public List<Nhunk> GetNhunks(string source, string target)
		{
			TestCounter = 0;
			List<Nhunk> nhunks = new List<Nhunk>();
			nhunks.Add(Nhunk.StartHunk);
			nhunks.Add(Nhunk.GetEndHunk(source.Length, target.Length));
			int listPointer = 1;
			RecurseGetNhunks(source, 0, target, 0, nhunks, listPointer);
			return nhunks;
		}

		private List<Nhunk> RecurseGetNhunks(string source, int sourceOffset, string target, int targetOffset, List<Nhunk> nhunks, int listPointer)
		{
			Nhunk nhunk = GetLongestNhunk(source, target);
			nhunk.SourceStart += sourceOffset;
			nhunk.TargetStart += targetOffset;
			if (nhunk.Length != 0)
			{
				Nhunk nhunkBefore = nhunks[listPointer - 1];
				Nhunk nhunkAfter = nhunks[listPointer];

				nhunks.Insert(listPointer, nhunk);

				// process remainder left:
				string leftSource = source.Substring(nhunkBefore.SourceEnd - sourceOffset, nhunkBefore.GetSourceLengthBetween(nhunk));
				string leftTarget = target.Substring(nhunkBefore.TargetEnd - targetOffset, nhunkBefore.GetTargetLengthBetween(nhunk));

				RecurseGetNhunks(leftSource, nhunkBefore.SourceEnd, leftTarget, nhunkBefore.TargetEnd, nhunks, nhunks.IndexOf(nhunk));

				// process remainder right:
				string rightSource = source.Substring(nhunk.SourceEnd - sourceOffset, nhunk.GetSourceLengthBetween(nhunkAfter));
				string rightTarget = target.Substring(nhunk.TargetEnd - targetOffset, nhunk.GetTargetLengthBetween(nhunkAfter));

				RecurseGetNhunks(rightSource, nhunk.SourceEnd, rightTarget, nhunk.TargetEnd, nhunks, nhunks.IndexOf(nhunk) + 1);
			}
			return nhunks;
		}


		public Nhunk GetLongestNhunk(string left, string right)
		{
			charPositions = new Dictionary<char, List<int>>();

			char[] rightChars = right.ToCharArray();
			char[] leftChars = left.ToCharArray();
			for (int i = 0; i < rightChars.Length; i++)
			{
				char rc = rightChars[i];
				if (!charPositions.ContainsKey(rc))
					charPositions[rc] = new List<int>();
				charPositions[rc].Add(i);
			}
			int maxl = 0;
			Nhunk lss = new Nhunk(0, 0, 0, string.Empty);
			for (int i = 0; i < leftChars.Length - maxl; i++)
			{
				if (charPositions.ContainsKey(leftChars[i]))
					foreach (int pos in charPositions[leftChars[i]])
					{
						int l = GetSubStringLength(left, i, right, pos);
						if (l > maxl)
						{
							maxl = l;
							lss = new Nhunk(i, pos, l, left.Substring(i, l));

						}
					}
			}
			return lss;
		}



		private int GetSubStringLength(string left, int i, string right, int pos)
		{
			int length = 0;

			while (length < left.Length - i && length < right.Length - pos &&
				left.Substring(length + i, 1) == right.Substring(length + pos, 1))
			{
				TestCounter++;
				length++;
			}
			return length;
		}

		public class Nhunk
		{
			public int SourceStart;
			public int TargetStart;
			public int Length;
			public string Text;


			public Nhunk(int ss, int ts, int l)
				: this(ss, ts, l, string.Empty)
			{ }

			private Nhunk(int ss, int ts)
				: this(ss, ts, 0, string.Empty)
			{ }

			public Nhunk(int ss, int ts, int l, string t)
			{
				SourceStart = ss;
				TargetStart = ts;
				Length = l;
				Text = t;
			}

			public int GetSourceLengthBetween(Nhunk upperSourceNhunk)
			{
				return upperSourceNhunk.SourceStart - this.SourceEnd;
			}
			public int GetTargetLengthBetween(Nhunk upperTargetNhunk)
			{
				return upperTargetNhunk.TargetStart - this.TargetEnd;
			}

			public int SourceEnd
			{ get { return SourceStart + Length; } }

			public int TargetEnd
			{ get { return TargetStart + Length; } }

			public static Nhunk StartHunk
			{
				get { return new Nhunk(0, 0); }
			}
			public static Nhunk GetEndHunk(int leftLength, int rightLength)
			{
				return new Nhunk(leftLength, rightLength);
			}

		}


	}
}